//
//  SortAlgorithm.c
//  algorithm
//
//  Created by 张俊正（总行零售网金） on 2020/6/17.
//  Copyright © 2020 sunshinfight. All rights reserved.
//

#include "SortAlgorithm.h"
#include <stdbool.h>
#include <stdlib.h>

// 冒泡, 属于交换排序
void sinkSort(int nums[], int count) {
    bool isFinished = false;
    int index = 0;
    while (index < count) {
        if (isFinished) {
            return;
        }
        isFinished = true;
        for (int i = 0; i < count - index - 1; i++) {
            if (nums[i] > nums[i+1]) {
                int tmp = nums[i];
                nums[i] = nums[i+1];
                nums[i+1] = tmp;
                isFinished = false;
            }
        }
        index++;
    }
}


void simpleSelectSort(int nums[], int count) {
    if (count <= 0) {
        return;
    }
    int loop = 0;
    while (loop < count - 1) {
        int minItemIndex = loop;
        int index = loop + 1;
        while (index < count) {
            if (nums[index] < nums[minItemIndex]) {
                minItemIndex = index;
            }
            index++;
        }
        int tmp = nums[minItemIndex];
        nums[minItemIndex] = nums[loop];
        nums[loop] = tmp;
        loop++;
    }
}


void simpleInsertSort(int nums[], int count) {
    if (count <= 0) {
        return;
    }
    for (int loop = 1; loop < count; loop++) {
        int num = nums[loop];
        int i = loop - 1;
        while(i >= 0) {
            if (nums[i] > num) {
                nums[i+1] = nums[i];
                nums[i] = num;
            }
            i--;
        }
    }
}

void shellSort(int nums[], int count) {
    for(int gap = count/2; gap > 0; gap/=2) {
        for (int i = gap; i < count; i++) {
            int j = i;
            int current = nums[i];
            while(j - gap >= 0 && current < nums[j-gap]) {
                nums[j] = nums[j-gap];
                j -= gap;
            }
            nums[j] = current;
        }
    }
}


void quickSort(int nums[], int left, int right) {
    if (left >= right) {
        return;
    }
    
    int pivot = nums[left];
    
    int i = left;
    int j = right;
    while (i < j) {
        while (j > i && nums[j] >= pivot) {
            j--;
        }
        while (i < j && nums[i] <= pivot) {
            i++;
        }
        if (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    nums[left] = nums[j];
    nums[j] = pivot;
    quickSort(nums, left, j - 1);
    quickSort(nums, j + 1, right);
}

int kThMaxValue(int nums[], int left, int right, int k) {
    if (left > right) {
        exit(1);
    }
    
    int pivot = nums[left];
    
    int i = left;
    int j = right;
    while (i < j) {
        while (j > i && nums[j] >= pivot) {
            j--;
        }
        while (i < j && nums[i] <= pivot) {
            i++;
        }
        if (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    nums[left] = nums[j];
    nums[j] = pivot;
    if (k < j) {
        return kThMaxValue(nums, left, j - 1, k);
    } else if (k > j) {
        return kThMaxValue(nums, j + 1, right, k);
    } else {
        return nums[j];
    }
}

void merge(int nums[], int left, int right, int mid) {
    int *ary = malloc((right - left + 1) * sizeof(int));
    int tmpIndex = 0;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (nums[i] < nums[j]) {
            ary[tmpIndex++] = nums[i++];
        } else {
            ary[tmpIndex++] = nums[j++];
        }
    }
    while (i <= mid) {
        ary[tmpIndex++] = nums[i++];
    }
    while (j <= right) {
        ary[tmpIndex++] = nums[j++];
    }
    for (int i = left, j = 0; i <= right; i++, j++) {
        nums[i] = ary[j];
    }
    free(ary);
}

void mergeSort(int nums[], int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, right, mid);
}

// 调整局部有序的小顶堆
void constructHeap(int nums[], int count, int rootIndex) {
    int i = rootIndex * 2 + 1;  // 左节点
    int j = rootIndex * 2 + 2;
    int nextRootIndex = rootIndex;
    if (i < count && nums[nextRootIndex] > nums[i]) {
        nextRootIndex = i;
    }
    if (j < count && nums[nextRootIndex] > nums[j]) {
        nextRootIndex = j;
    }
    if (nextRootIndex != rootIndex) {
        int tmp = nums[rootIndex];
        nums[rootIndex] = nums[nextRootIndex];
        nums[nextRootIndex] = tmp;
        constructHeap(nums, count, nextRootIndex);
    }
}

void heapSort(int nums[], int count) {
    int start = count / 2 - 1;
    while (start >= 0) {
        constructHeap(nums, count, start);
        start--;
    }
    for (int i = count - 1; i > 0; i--) {
        int tmp = nums[i];
        nums[i] = nums[0];
        nums[0] = tmp;
        constructHeap(nums, i, 0);
    }
}


void countSort(int nums[], int count, int maxRange) {
    int *tmpAry = calloc(maxRange + 1, sizeof(int));
    for (int i = 0; i < count; i++) {
        tmpAry[nums[i]]++;
    }
    int numsIndex = 0;
    for (int i = 0; i < maxRange + 1; i++) {
        for (int j = 0; j < tmpAry[i]; j++) {
            nums[numsIndex++] = i;
        }
    }
    free(tmpAry);
}
